package code.class3;


import java.util.Arrays;

/**
 * https://leetcode.cn/problems/boats-to-save-people/
 * 救生艇问题
 * 每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
 *
 * 解题思路：
 * 1.先从轻到重排序
 * 2.判断首尾相加是否大于载重
 */
public class Code06_numRescueBoats {
    public static void main(String[] args) {
        int[] arr = {5, 4, 2, 8, 5, 6, 3, 7};
        int limit = 10;
        int boats = numRescueBoats(arr, limit);
        System.out.println("boats = " + boats);
    }

    public static int numRescueBoats(int[] arr, int limit) {
        int ans = 0, l = 0, r = arr.length - 1;
        // 从小到大排序
        Arrays.sort(arr);
        while (l <= r) {
            // 当l==r时，只取一个位置上的数。
            // 否则取arr[l] + arr[r]
            int sum = l == r ? arr[l] : arr[l] + arr[r];
            if (sum <= limit) {
                // 移动指针
                l++;
                r--;
            } else {
                // 当sum>limit时，说明最大值已经不能和任何最小值相加了，只能arr[r]自己乘坐一艘船，r--
                r--;
            }
            ans++;
        }
        return ans;
    }

}
